1. Field of the Invention
This invention relates generally to communication encoders, decoders, transmitters, receivers, and systems. More particularly, aspects of the invention relate a family of encoders and a family of decoders that make use of constrained interleaving with various forms of serially concatenated codes.
2. Description of the Related Art
Various forms of concatenated codes are known in the art. Turbo codes are widely used and represent parallel concatenated codes. In the literature, interleaver design has been discussed with both parallel and serial concatenation but mainly in connection with parallel concatenated codes. For example, see [1] J. Yu, M.-L. Boucheret, R. Vallet, A. Duverdier and G. Mesnager, “Interleaver design for serial concatenated convolutional codes”, IEEE Commun. Letters, Vol. 8, No. 8, pp. 523-525, August 2004; [2] F. Daneshgaran, M. Laddomada and M. Mindin, “Interleaver design for serially concatenated convolutional codes: Theory and application”, IEEE Trans. On Inform Theory, vol. 50, No. 6, pp. 1177-1188, June 2004; [3] H. R. Sadjadpour, N. J. A. Sloane, G. Nebe and M. Salehi, “Interleaver design for turbo codes”, in proc. ISIT, pp. 453, June 2000; and [4] H. R. Sadjadpour, N.J.A. Sloane, M. Salehi and G. Nebe, “Interleaver design for turbo codes”, IEEE Journal of selected areas in Commun., vol. 19, pp. 831-837, May 2001, as supplied on the IDS herewith.
The above design approaches start from uniform interleaving and modify the uniform interleaver's probability distribution according to various rules. A “uniform Interleaver” is defined by a randomization operation of the form Output=Rand(Input) where Input and Output represent respective vectors of N elements, and Rand is a function that pseudo randomly permutes the order of the elements in the vector Input. In most cases, the prior art uniform interleaver is a “bit interleaver” and the elements of Input and Output represent bits. That is, the uniform interleaver is used to randomize the order of a set of input bits to create a randomized-ordered set of output bits.
While uniform interleaving or its variants as referenced above may be the best ways to construct interleavers for use with parallel concatenated codes, it would be desirable to have a different form of interleaving that takes advantage of correlations that exist in coded bits that have been formed via serial concatenation encoding. Unlike parallel concatenation, where interleaving is performed on pure uncorrelated information bits which are usually independent, in the case of serial concatenation, the interleaver is used on the coded bits of the outer code which are correlated due to the outer code. It would be desirable to have an interleaving technique for use with serial concatenation that exploits the correlation of the coded bits introduced by the outer code. It would be desirable if interleavers designed to exploit that correlation were able to have much shorter interleaver lengths while being able to perform as well or better than much longer interleavers that are designed using prior art approaches that amount to variants of uniform interleaving.
FIG. 1 shows a prior art turbo encoder. As can be seen from the parallel structure of FIG. 1, Turbo encoders are based on parallel concatenation. The message bits are replicated and processed on three (or in general, more) paths. The first path has no coding, the second path encodes the message bits with Encoder #1 which is usually a convolutional code, and the third path uniform interleaves the message bits and then encodes the interleaved message bits with Encoder #2. Three times as many bits are produced using this parallel approach, resulting in a rate 1/3 code. Code puncturing can be optionally used to increase the rate of the concatenated code. Turbo codes are usually decoded using an iterative decoder structure similar to the one shown in FIG. 5 with the constrained interleavers/deinterleavers replaced with uniform interleavers/deinterleavers. The soft decoder of FIG. 5 uses the well known BJCR algorithm or some other type of soft decoding algorithm in its soft decoding blocks.
FIG. 2 shows the serial structure of a prior art serial concatenated encoder. The message bits are first encoded by an outer encoder, then the outer-encoded bits are sent through a uniform interleaver, and the interleaved outer-encoded bits are next passed through an inner encoder. In general, more than two component codes can be concatenated together, but, without loss of generality, the discussion herein focuses on embodiments that make use of two serially concatenated component codes. The concepts presented herein can be extrapolated to these higher order cases by induction. In many practical cases the outer code is a block code or a nonrecursive convolutional code and the inner code is a recursive convolutional code. Serial concatenated codes are also usually decoded using an iterative decoder structure similar to the one shown in FIG. 5 with the constrained interleavers/deinterleavers replaced with uniform interleavers/deinterleavers.
It is known that serially concatenated codes and parallel concatenated codes can both be designed to achieve interleaver gain. “Interleaver gain” is defined as a reduction in the bit error rate as the interleaver length, N, is increased. This occurs because certain dominant error coefficients in the probability of error expression are reduced as N is increased. It is known in the art that serially concatenated codes can be designed to perform better than parallel concatenated codes with similar parameters. Serial concatenation can employ component codes that are block and/or convolutional codes. General design rules of serially concatenated codes are well known. It is generally advantageous to use an outer code that has a high minimum Hamming distance and to employ a recursive inner code. However, it is also known that even though the traditional method of serial concatenation is done using recursive inner codes, block codes can also be effectively used for the inner code as well; for example, see [5] M. Sikora and J. Costello, Jr., “Serial concatenation with simple block inner codes”, in proc. ISIT, pp. 1803-1807, July 2006. Serially concatenated codes can be decoded using iterative soft decoding of inner and outer codes (using a structure similar to that shown in FIG. 5 but with a uniform interleaver such as one that may be implemented using a randomization function with a uniform distribution or e.g., see [1]-[4]).
More background information on serial concatenated codes that supports the discussion in the above paragraph can be found in: [6] S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara, “Serial concatenation of interleaved codes: Performance analysis, design and iterative decoding”, IEEE Trans., Inform. Theory, vol. 44, pp. 909-926, May 1998 [7] S. Benedetto, D. Divsalar, G. Montrosi and F. Pollara, “Analysis, design, and iterative decoding of double serially concatenated codes with interleavers”, IEEE Journal on Selected Areas in Commun., vol. 16, No. 2, pp. 231-244. February 1998; [8] S. Benedetto and G. Montrosi, “Iterative decoding of serially concatenated convolutional codes”, Electronics Letters, vol. 32, No. 13, pp. 1186-1188, June 1996; [9] S. Benedetto, D. Divsalar, G. Montrosi and F. Pollara, “A soft-input soft-output APP module for iterative decoding of concatenated codes”, IEEE Commun. Letters, pp. 22-24. January 1997; and [10] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes”, IEEE Trans. Inform. Theory, vol. 42, pp. 429-445, March 1996; all of which are included on the IDS submitted herewith. For further background information on both serial and parallel concatenated codes, also see S. Lin and D. Costello, Jr., Error Control Coding: Fundamentals and Applications, 2nd Ed., Pearson Prentice-Hall, 2004.
Multi-dimensional SPC codes are also well known in the art. It is known that uniform interleaving can be applied in some cases to improve the performance of these codes, but not in other cases such as 2-dimensional SPC codes. See for example: [11] D. M. Rankin and T. A. Gulliver, “Single parity check product codes”, IEEE Trans. On Commun., vol. 49, pp. 1354-1362, August 2001; [12] X. R. Ma and Y. Y. Xu, “Iterative decoding of parallel and serial concatenated single parity check product codes”, Electronics Letters, vol. 42, No. 15, pp. 869-870, July 2006; [13] L. Ping, S. Chan and K. L. Yeung, “Efficient soft-in-soft-out sub-optimal decoding rule for single parity check codes”, Electronics Letters, vol. 33, No. 19, pp. 1614-1616, September 1997; [14] D. Rankin and A. Gulliver, “Randomly interleaved SPC product codes”, in Proc. ISIT, pp. 88, 2000; and [15] D. M. Rankin, T. A. Gulliver and D. P. Taylor, “Parallel and serial concatenated single parity check product codes”, EURASIP Journal on Applied Signal Processing, pp. 775-783, January 2005.
It would be desirable to improve the performance of 2-dimensional SPC codes using an inventive constrained interleaver. It would be desirable to be able to use shorter interleavers to provide the same or improved performance over SPCs that currently use uniform interleavers.
In both parallel and serially concatenated codes, the design objective traditionally has been to focus on the interleaver gain that affects the error coefficient as opposed to the minimum distance of the resulting concatenated code. This makes sense when it is tolerable to employ long interleavers. However, due to the increase in the complexity, memory requirements and delay caused by long interleavers, in practice it is preferable to avoid making the size of the interleaver too large. While it would be desirable to consider the minimum distance of the overall code for short to moderate interleaver sizes, it is conventional wisdom that the joint consideration of both the minimum distance and the interleaver design is too difficult to handle [6]. It would be desirable to develop a technique to improve bit error rate performance by introducing an interleaver constraint that has the effect of jointly optimizing or otherwise jointly considering both the minimum distance and the reduction of dominant error coefficients. It would be desirable to have a new technology that used such interleaver constraints to design more efficient encoders and decoders for various forms of serially concatenated codes.